/*https://leetcode.cn/problems/count-ways-to-build-good-strings/submissions/562788938/
统计构造好字符串的方案数
24/9/6
*/


#include <vector>

class Solution {
public:
    int countGoodStrings(int low, int high, int zeroLength, int oneLength) {
        const int MOD = 1e9 + 7; // 模数，用于防止溢出
        std::vector<int> dp(high + 1, 0); // 动态规划数组，dp[i] 表示长度为 i 的好字符串的数量
        int result = 0; // 最终结果

        // 初始化 dp[0]，空字符串也是一种有效的好字符串
        dp[0] = 1;

        // 计算从 0 到 max(zeroLength, oneLength) 的好字符串数量
        int maxLen = std::max(zeroLength, oneLength);
        for (int i = zeroLength; i <= maxLen; i += zeroLength) {
            dp[i] += 1;
        }
        for (int i = oneLength; i <= maxLen; i += oneLength) {
            dp[i] += 1;
        }

        // 动态规划计算从 maxLen + 1 到 high 的好字符串数量
        for (int i = maxLen + 1; i <= high; i++) {
            dp[i] = (dp[i - oneLength] + dp[i - zeroLength]) % MOD;
        }

        // 计算长度在 [low, high] 范围内的所有好字符串的数量
        for (int i = low; i <= high; i++) {
            result = (result + dp[i]) % MOD;
        }

        return result;
    }
};